<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    289. Game of Life
   </h1>
   <p>
    According to the
    <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" target="_blank">
     Wikipedia's article
    </a>
    : "The
    <b>
     Game of Life
    </b>
    , also known simply as
    <b>
     Life
    </b>
    , is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
   </p>
   <p>
    Given a
    <i>
     board
    </i>
    with
    <i>
     m
    </i>
    by
    <i>
     n
    </i>
    cells, each cell has an initial state
    <i>
     live
    </i>
    (1) or
    <i>
     dead
    </i>
    (0). Each cell interacts with its
    <a href="https://en.wikipedia.org/wiki/Moore_neighborhood" target="_blank">
     eight neighbors
    </a>
    (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
   </p>
   <ol>
    <li>
     Any live cell with fewer than two live neighbors dies, as if caused by under-population.
    </li>
    <li>
     Any live cell with two or three live neighbors lives on to the next generation.
    </li>
    <li>
     Any live cell with more than three live neighbors dies, as if by over-population..
    </li>
    <li>
     Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
    </li>
   </ol>
   <p>
    Write a function to compute the next state (after one update) of the board given its current state.&nbsp;
    <span>
     The next state is created by applying the above rules simultaneously to every cell in the current state, where&nbsp;births and deaths occur simultaneously.
    </span>
   </p>
   <p>
    <strong>
     Example:
    </strong>
   </p>
   <pre>
<strong>Input: 
</strong><span id="example-input-1-1">[
&nbsp; [0,1,0],
&nbsp; [0,0,1],
&nbsp; [1,1,1],
&nbsp; [0,0,0]
]</span>
<strong>Output: 
</strong><span id="example-output-1">[
&nbsp; [0,0,0],
&nbsp; [1,0,1],
&nbsp; [0,1,1],
&nbsp; [0,1,0]
]</span>
</pre>
   <p>
    <b>
     Follow up
    </b>
    :
   </p>
   <ol>
    <li>
     Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
    </li>
    <li>
     In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    289. 生命游戏
   </h1>
   <p>
    根据
    <a href="https://baike.baidu.com/item/%E7%94%9F%E5%91%BD%E6%B8%B8%E6%88%8F/2926434?fr=aladdin" target="_blank">
     百度百科
    </a>
    ，生命游戏，简称为生命，是英国数学家约翰&middot;何顿&middot;康威在1970年发明的细胞自动机。
   </p>
   <p>
    给定一个包含 m &times; n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态
    <em>
     live
    </em>
    （1）即为活细胞， 或
    <em>
     dead
    </em>
    （0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
   </p>
   <ol>
    <li>
     如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
    </li>
    <li>
     如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
    </li>
    <li>
     如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
    </li>
    <li>
     如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
    </li>
   </ol>
   <p>
    根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
   </p>
   <p>
    <strong>
     示例:
    </strong>
   </p>
   <pre><strong>输入: 
</strong>[
&nbsp; [0,1,0],
&nbsp; [0,0,1],
&nbsp; [1,1,1],
&nbsp; [0,0,0]
]
<strong>输出: 
</strong>[
&nbsp; [0,0,0],
&nbsp; [1,0,1],
&nbsp; [0,1,1],
&nbsp; [0,1,0]
]</pre>
   <p>
    <strong>
     进阶:
    </strong>
   </p>
   <ul>
    <li>
     你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
    </li>
    <li>
     本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
    </li>
   </ul>
  </div>
 </body>
</html>